//
//  ProblemOffer36.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/5.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 36. 二叉搜索树与双向链表
 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

 为了让您更好地理解问题，以下面的二叉搜索树为例：
 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

 下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

 特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
 */
@objcMembers class ProblemOffer36: NSObject {
    func solution() {
        let root = TreeNode(4)
        root.left = TreeNode(2)
        root.left?.left = TreeNode(1)
        root.left?.right = TreeNode(3)
        
        root.right = TreeNode(5)
        
        treeToDoublyList(root)
    }
    func treeToDoublyList(_ root: TreeNode?) -> TreeNode? {
//        let (header, _) = treeToDoublyListDFS(root)
//        return header
        
        if root == nil {
            return nil
        }
        
        treeToDoublyListDFS2(root)
        head?.left = tail
        tail?.right = head
        return head
    }
    
    // 递归
    func treeToDoublyListDFS(_ root: TreeNode?) -> (TreeNode?, TreeNode?) {
        if root == nil {
            return (nil, nil)
        } else if root?.left == nil && root?.right == nil {
            return (root, root)
        }
        
        var header: TreeNode? = nil
        let (leftHeader, leftTail) = treeToDoublyListDFS(root?.left)
        
        if leftHeader == nil {
            header = root
        } else {
            header = leftHeader
            leftTail?.right = root
        }
        
        var tail: TreeNode? = nil
        let (rightHeader, rightTail) = treeToDoublyListDFS(root?.right)
        
        if rightHeader == nil {
            tail = root
        } else {
            root?.right = rightHeader
            tail = rightTail
        }
        header?.left = tail
        tail?.right = header
        
        return (header, tail)
    }
    
    // 使用成员变量递归
    var head: TreeNode?
    var tail: TreeNode?
    func treeToDoublyListDFS2(_ root: TreeNode?) {
        if root == nil {
            return
        }
        
        treeToDoublyListDFS2(root?.left)
        
        if head == nil {
            head = root
        } else {
            tail?.right = root
        }
        
        root?.left = tail
        tail = root
        treeToDoublyListDFS2(root?.right)
    }
}
